// https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 快慢指针法，slow指向已处理序列末尾
// 2. 检查nums[slow-2]与当前元素是否相等
// 3. 不相等时保留当前元素，相等时跳过（已重复两次）
// 4. 最终slow即为新数组长度
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    int removeDuplicates(vector<int>& nums) 
    {
        int m = nums.size();
        if (m <= 2) return m;

        int index = 2;
        for (int i = 2 ; i < m ; i++)
        {
            if (nums[index - 2] != nums[i])
            {
                nums[index++] = nums[i];
            }
        }

        return index;
    }
};

int main()
{
    vector<int> nums1 = {1,1,1,2,2,3}, nums2 = {0,0,1,1,1,1,2,3,3};
    Solution sol;

    int len1 = sol.removeDuplicates(nums1);
    int len2 = sol.removeDuplicates(nums2);

    for (int i = 0 ; i < len1 ; i++)
        cout << nums1[i] << " ";
    cout << endl;

    for (int i = 0 ; i < len2 ; i++)
        cout << nums2[i] << " ";
    cout << endl;

    return 0;
}